In an IC design flow based on a cell-based library, hardware descriptions such as Verilog's netlist are used to describe involving standard logic cells and nets. The netlist is then processed for physical design. Meanwhile, 2-pin logic cells are commonly used in the physical design for specific circuitry requirements and integrated signal transmission.
A generally adopted placement stage of IC logic cells includes placement of standard logic cells based on a timing driven strategy and a wire-length driven strategy.
In the so-called timing driven strategy, signal path delay time indicative of a duration when a signal is transmitted from an input end to an output end of each signal transmission path is calculated in order to determine the placement sequence of the standard logic cells. Among a plurality of paths, the path involving a longer signal path delay time has a higher priority to be placed so that the standard logic cells in that path is made closer to one another compared to those in other paths. In this way, the overall propagation delay in the physical circuit can be reduced.
On the other hand, in the so-called wire-length driven strategy, signal routing length indicative of a distance from an input end to an output end of each signal transmission path is calculated in order to determine the placement sequence of the standard logic cells. Among a plurality of paths, the path involving a longer signal routing length has a higher priority to be placed so that the standard logic cells in that path is made closer to one another compared to those in other paths. In this way, the overall routing length in the physical circuit can be reduced.
However, none of the current computer-aided design tools involves optimized orientation of 2-bin logic cells to further reduce propagation delay and routing length. It is desirable to implement the optimization of orientation prior to or following the placement stage with a feature of single input and single output, which is further advantageous in avoiding wire crossing.
Please refer to FIG. 1A. A signal transmission path inclusive of 2-pin logic cells without orientation optimization after the placement stage is exemplified. In the figure, relatively large rectangles represent 2-pin logic cells including a first 2-pin logic cell L1, a second 2-pin logic cell L2, and a third 2-pin logic cell L3. The circles in each 2-pin logic cell indicates its input terminal (in) and output terminal (out); and the squares are vias V1˜V13 for connecting different metal layers.
As shown in FIG. 1A, signal transmission is performed rightwards and passes the first 2-pin logic cell L1, the second 2-pin logic cell L2, and the third 2-pin logic cell L3 in sequence. The input in of the first 2-pin logic cell L1 is disposed at the right side and coupled to the output out0 of a preceding stage of 2-pin logic cell (not shown); the output out1 of the first 2-pin logic cell L1 is disposed at the left side and coupled to the input in2 of the second 2-pin logic cell L2 disposed at the right side; the output out2 of the second 2-pin logic cell L2 is disposed at the left side and coupled to the input in3 of the third 2-pin logic cell L3 disposed at the right side; and the output out3 of the third 2-pin logic cell L3 is disposed at the left side and coupled to the input in4 of next stage of 2-pin logic cell L3 (not shown).
It is apparent that wire crossing occurs in the above-described signal transmission path. Practically, plural metal layers and vias are essential to wiring procedures in an IC manufacturing process. For example, Via number 0 (V0), Via number 1 (V1), Via number 2 (V2), Via number 3 (V3), Via number 4 (V4), Via number 5 (V5) and Via number 6 (V6) are used to connect a first metal layer to a second metal layer; and Via number 7 (V7), Via number 8 (V8), Via number 9 (V9), Via number 10 (V10), Via number 11 (V11), Via number 12 (V12) and Via number 13 (V13) are used to connect the second metal layer to a third metal layer. Furthermore, a wire m0 is a wire of the first metal layer; wires m1, m3, m4, m6, m7, m9 and m10 are wires of the second metal layer; and wires m2, m5, m8 and m11 are wires of the third metal layer.
In other words, the input in1 of the first 2-pin logic cell L1 is coupled to the output out0 of the preceding stage through the via V2, the wire m3 of the second metal layer, the via V9, the wire m2 of the third metal layer, the via V7, the wire m1 of the second metal layer, the via V0 and the wire m0 of the first metal layer; the output out1 of the first 2-pin logic cell L1 is coupled to the input in2 of the second 2-pin logic cell L2 through the via V1, the wire m4 of the second metal layer, the via V8, the wire m5 of the third metal layer, the via V11, the wire m6 of the second metal layer, and the via V4; and so on. The output out3 of the third 2-pin logic cell L3 is coupled to the input in4 of the next stage through the via V5, the wire m10 of the second metal layer, the via V12, and the wire m11 of the third metal layer.
It can be seen from the above example that without orientation optimization, three metal connecting layers and fourteen vias are required for the connection between the output out0 of the preceding stage and the input in4 of the next stage. The connection among cells is quite complicated.
With orientation optimization of logic cells during the placement stage, the connection would become that shown in FIG. 1B. That is, all the input terminals (in1, in2, in3) of the first 2-pin logic cell L1, the second 2-pin logic cell L2, and the third 2-pin logic cell L3 are disposed at respective left sides; and all the output terminals (out1, out2, out3) of the first 2-pin logic cell L1, the second 2-pin logic cell L2, and the third 2-pin logic cell L3 are disposed at respective right sides. Apparently, wire crossing is diminished, and only wires m0, m1, m2 and m3 are required for the connection between the output out0 of the preceding stage and the input in4 of the next stage.
Comparing the situation shown in FIG. 1A with that shown in FIG. 1B, it is understood that orientation optimization performed at proper timing may practically reduce the overall routing length. However, an IC generally includes tens to hundreds of thousand 2-pin logic cells, and the interconnection among the cells is variable instead of always lining left to right. Other circuitry such as a clock tree including a series of buffers is even formed with branches which are variously oriented paths. Therefore, it is a challenge to properly adjust the orientation of the cells.
An orientation optimization method was proposed in the Design Automation Conference held in USA in 2006. The method has a “Nets-based flip” structure, which will be described hereinafter with reference to FIG. 2A˜2D.
In the case of FIG. 2A, a first 2-pin logic cell L1 in a first stage needs to transmit signals to three second-stage 2-pin logic cells, which are arranged up to down in sequence as the second 2-pin logic cell L2, the third 2-pin logic cell L3 and the fourth 2-pin logic cell L4. As shown, the input (in1) of the first 2-pin logic cell L1 is disposed at the left side while the output (out1) is disposed at the right side; the input (in2) of the second 2-pin logic cell L2 is disposed at the left side while the output (out2) is disposed at the right side; the input (in3) of the third 2-pin logic cell L3 is disposed at the right side while the output (out3) is disposed at the left side; and the input (in4) of the fourth 2-pin logic cell L4 is disposed at the left side while the output (out4) is disposed at the right side. By connecting the output (out1) of the first 2-pin logic cell L1 with the inputs (in1, in2, in3) of the three second-stage 2-pin logic cells L2, L3 and L4, a net bounding box 21 is defined.
Please refer to FIG. 2A. Solid lines are used to show the net bounding box 21 connecting the output (out1) of the first 2-pin logic cell L1 with the inputs (in1, in2, in3) of the three second-stage 2-pin logic cells L2, L3 and L4. In contrast, dash lines are used to show the shortest distance of connection. It can be seen from the illustration that the shortest routing length required to connect these logic cells is a half of the circumference of the net bounding box 21 (half perimeter bounding box).
In principle, the smaller the net bounding box, the shorter the routing length. Therefore, it would be desired to flip the third 2-pin logic cell L3 along the Y-axis. That is, the input (in3) of the third 2-pin logic cell L3 is made to be disposed at the left side, and the output (out3) is made to be disposed at the right side. Accordingly, a new net bounding box 22 is obtained. In brief, nets-based flip is to locate a net bounding box, and properly flip one or more 2-pin logic cells involved to realize a smallest net bounding box so as to minimize the routing length.
Nevertheless, it is to be noted that according to the “nets-based flip” method, the flip of a cell is forbidden if the flip resulting in the size reduction of a net bounding box meanwhile results in size enlargement of a net bounding box in next stage. It is because the overall routing length might be contrarily enlarged.
For example, referring to FIG. 2C, the output (out3) of the third 2-pin logic cell L3 in the second stage is further connected to inputs (in5, in6) of two 2-pin logic cells L5 and L6 in the third stage, wherein the input (in5) of the fifth 2-pin logic cell L5 is disposed at the right side while the output (out5) is disposed at the left side; the input (in6) of the sixth 2-pin logic cell L6 is disposed at the right side while the output (out6) is disposed at the left side. As shown, the 2-pin logic cells in the first and the second stages form the net bounding box 21 while those in the second and third stages form another net bounding box 23.
For reducing the size of the net bounding box 21, it is intended to flip the third 2-pin logic cell L3. That is, the input (in3) of the third 2-pin logic cell L3 is changed to be disposed at the left side, and the output (out3) is changed to be disposed at the right side, as shown in FIG. 2D. Accordingly, the new net bounding box 22 with a reduced size is obtained. However, the size of another new net bounding box 24 derived from the third net bounding box due to the flip of the third 2-pin logic cell L3 is enlarged. Thus the flip is forbidden according to the definition of conventional “nets-based flip” algorithm.
In addition to the above-described “nets-based flip” structure, U.S. Patent Publication No. US2007/0204252 also suggests an improved “nets-based flip” method, which is to be incorporated herein for reference.
Nevertheless, the conventional “nets-based flip” methods have difficulties in dealing with a situation that signal transmission is implemented with branched paths so that the conventional “nets-based flip” methods could not accurately determine the 2-pin logic cell in which stage is to be flipped.
A clock tree exemplified in FIG. 3A is used for illustrating branched paths. First of all, for equalizing delay time of clock signals, the 2-pin logic cells of the clock tree are allocated to form an H-shaped tree (H tree). As shown, a clock signal is transmitted from a first 2-pin logic cell L1 to a second 2-pin logic cell L2, and then four branched clock signals are transmitted from the second 2-pin logic cell L2 to a third 2-pin logic cell L3, a fourth 2-pin logic cell L4, a fifth 2-pin logic cell L5 and a sixth 2-pin logic cell L6, following H-tree paths.
Subsequently, at the ends of the branched paths, clock signals are transmitted from the outputs (out3, out4, out5, out6) of the 2-pin logic cells L3, L4, L5 and L6 to respective four standard logic cells in need of the clock signals. The four standard logic cells associated with the third 2-pin logic cell L3 are connected to the output (out3) of the third 2-pin logic cell L3 with respective inputs clk3a, clk3b, clk3c and clk3d. The four standard logic cells associated with the third 2-pin logic cell L4 are connected to the output (out4) of the third 2-pin logic cell L4 with respective inputs clk4a, clk4b, clk4c and clk4d. Likewise, the four standard logic cells associated with the third 2-pin logic cell L5 are connected to the output (out5) of the third 2-pin logic cell L5 with respective inputs clk5a, clk5b, clk5c and clk5d; and the four standard logic cells associated with the third 2-pin logic cell L6 are connected to the output (out6) of the third 2-pin logic cell L6 with respective inputs clk6a, clk6b, clk6c and clk6d. The standard logic cells, for example, are D flip-flop cells including an input terminal (Din), an output terminal (Dout) and a clock input terminal (clk).
It can be seen from FIG. 3A that the clock signal path extends from the output (out1) of the first 2-pin logic cell L1 to the input (in2) of the second 2-pin logic cell L2, and then from the output (out2) of the second 2-pin logic cell L2 to respective inputs (in3, in4, in5, in6) of the four parallel 2-pin logic cells L3, L4, L5 and L6. In a case that three net bounding boxes are associated with the third 2-pin logic cell L3, e.g. a first net bounding box 31 of its input (in3) connecting the output (out2), the input (in3) and the input (in5), a second net bounding box 32 of its output (out3) connecting the output (out3), the input (clk3b) and the input (clk3d), and a third net bounding box 33 of its input (in3) connecting the output (out3), the input (clk3a) and the input (clk3c).
The net bounding boxes constructed without flipping are illustrated in FIG. 3B, while the net bounding boxes constructed with flipping are illustrated in FIG. 3C. As showing in FIG. 3C, the third 2-pin logic cells L3 and the fifth 2-pin logic cells L5 are flipped so as to make the inputs (in3, in5) closer to the output (out2) of the second 2-pin logic cells L2, thereby contracting the first net bounding box 31. Comparing FIG. 3C with FIG. 3B, the flip of the third 2-pin logic cells L3, although reducing the size of the first net bounding box 31, enlarging the size of the second net bounding box 32 at the same time. Therefore, the flipping is forbidden in principle.
It is to be noted that although the size of the second net bounding box 32 is enlarged along with the size reduction of the first net bounding box 31, the size of the third net bounding box 33 is simultaneously reduced. As a whole, the flipping is still advantageous because the size of the first net bounding box 31 is reduced and the changes of the second and third net bounding boxes 32 and 33 are offset. Therefore, it is improper to determine that a 2-pin logic cell should not be flipped simply due to the increasing size of the associated net bounding box in next stage.